package lc;

import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

public class Ex460_2 {
    class LFUCache {
        LFU lfu;

        public LFUCache(int capacity) {
            lfu = new LFU(capacity);
        }
        
        public int get(int key) {
            return lfu.get(key);
        }
        
        public void put(int key, int value) {
            lfu.put(key, value);
        }
    }

    class LFU {

        LFUNode head, tail;
        int capacity, size;
        Map<Integer, LFUNode> map1;
        Map<Integer, Node> map2;

        public LFU(int capacity) {
            this.capacity = capacity;
            this.size = 0;
            head = new LFUNode(Integer.MIN_VALUE);
            tail = new LFUNode(Integer.MAX_VALUE);
            head.next = tail;
            tail.next = head;
            map1 = new HashMap<>();
            map2 = new HashMap<>();
        }

        public int get(int key) {
            if (!map2.containsKey(key)) {
                return -1;
            }
            LFUNode dest = map1.get(key);
            LFUNode to = dest.getNext();
            if (to.freq != dest.freq + 1) {
                to = insertIntoNext(dest, dest.freq + 1);
            }
            Node node = map2.get(key);
            dest.remove(node);
            if (dest.isEmtpy()) {
                remove(dest);
            }
            to.add(node);
            map1.put(key, to);
            return node.val;
        }

        public void put(int key, int val) {
            if (this.capacity == 0) {
                return;
            }
            if (map2.containsKey(key)) {
                Node node = map2.get(key);
                node.val = val;
                this.get(key); //增加一次访问次数
            } else {
                Node node = new Node(key, val);
                LFUNode first = this.head.next;
                if (this.size < this.capacity) {
                    //直接插入
                    if (first.freq != 1) {
                        //1号节点不存在
                        first = insertIntoNext(head, 1);
                    }
                    first.add(node);
                    map1.put(key, first);
                    map2.put(key, node);
                    this.size++;
                } else {
                    //空间不足，删除最近最少使用的那个节点
                    Node removed = first.removeLast();
                    map1.remove(removed.key);
                    map2.remove(removed.key);
                    this.size--;
                    if (first.isEmtpy()) {
                        remove(first);
                    }
                    put(key, val);
                }
            }
        }

        public boolean isEmpty() {
            return head.next == tail;
        }

        public void remove(LFUNode node) {
            node.next.prev = node.prev;
            node.prev.next = node.next;
        }

        
        public LFUNode insertIntoNext(LFUNode cur, int freq) {
            LFUNode next = cur.next;
            LFUNode node = new LFUNode(freq);
            node.prev = cur;
            node.next = next;
            cur.next = node;
            next.prev = node;
            return node;
        }
    }

    class LFUNode {

        int freq;
        LRU lru;
        LFUNode prev, next;

        public LFUNode(int freq) {
            this.freq = freq;
            this.lru = new LRU();
        }


        public LFUNode getNext() {
            return this.next;
        }

        public void remove(Node node) {
            lru.remove(node);
        }

        public void add(Node node) {
            lru.insertIntoFirst(node);
        }

        public boolean isEmtpy() {
            return lru.isEmpty();
        }

        public Node removeLast() {
            return lru.removeLast();
        }
        
    }

    class Node {
        Node prev, next;
        int key, val;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    class LRU {

        Node head, tail;
        LRU prev, next;

        public LRU() {
            head = tail = new Node(-1, -1);
            head.next = tail;
            tail.prev = head;
        }

        public void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        public Node removeLast() {
            Node node = tail.prev;
            remove(node);
            return node;
        }

        public void insertIntoFirst(Node node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }

        public boolean isEmpty() {
            return head.next == tail;
        }
    }


    @Test
    public void test() {
            LFUCache lfu = new LFUCache(2);
            lfu.put(1, 1);
            lfu.put(2, 2);
            System.out.println(lfu.get(1));
            lfu.put(3, 3);
            System.out.println(lfu.get(2));
            System.out.println(lfu.get(3));
            lfu.put(4, 4);
            System.out.println(lfu.get(1));
            System.out.println(lfu.get(3));
            System.out.println(lfu.get(4));

        }

        /**
["LFUCache","put","get"]
[[0],[0,0],[0]]
         */

         @Test
         public void test2() {
            LFUCache lfu = new LFUCache(0);
            lfu.put(1, 1);
            lfu.put(2, 2);
            System.out.println(lfu.get(1));
             
         }

}
